This invention pertains to caches in computer systems, and more particularly to a method for replacing blocks in the cache.
Caches provide a closer, faster access to important information for the Central Processing Unit (CPU) of a computer. For example, caches are often used to store memory blocks that have been accessed recently by the CPU. But it is not practical to make caches large enough to store all of the available memory blocks. Aside from the obvious fact that such a large cache would make the main memory unnecessary, cache memory is more expensive than main memory. To keep costs down, caches tend to be small in size relative to main memory.
Because caches cannot store every block in main memory, when a new block needs to be allocated from the cache, the cache must use a replacement policy to decide what block currently in the cache is to be replaced. Various replacement policies are known in the art. The random replacement policy randomly selects an existing cache block to replace. The Least Recently Allocated (LRA, sometimes also called First In, First Out, or FIFO) replacement policy tracks how long each block has been in the cache and replaces the block that has been in the cache the longest. The Least Recently Used (LRU) replacement policy tracks how long it has been since each block in the cache has been used and replaces the block that has gone the longest since it was last used.
Assuming that the sequence of memory block misses is not known in advance, the LRU replacement policy generally provides the best performance. However, the LRU replacement policy is the most complicated replacement policy to implement. Information about each cache block access must be kept to maintain the order of cache block accesses, thus requiring fields to be updated at every access. The random and LRA replacement policies are easier to implement but provide poorer performance.
The present invention addresses this and other problems associated with the prior art.